Notes (Week 2 Monday)
These are the notes I wrote during the lecture.
E.g.
S = {1,2,3} and R = {2,1,3,1}
^ are considered to be the exact same set.
Because they have the same elements,
or more precisely:
because the exact same membership judgements are true about both
1 ∈ S 1 ∈ R
2 ∈ S 2 ∈ R
3 ∈ S 3 ∈ R
4 ∉ S 4 ∉ R
.........
The empty set
written {} or ∅
The empty set {} - no elements, because no membership judgement about it is true
The set containing the empty set {{}} - one element, because only one membership judgement is true
The set containing the set containing the empty set {{{}}} - one element,
{{}} ∈ {{{}}}
{} ∉ {{{}}}
Imagine a christmas present that's just an empty box (the empty set)
This is different from:
a christmas present, that when you unwrap it,
there's another christmas present in it, but that one is empty ({{}})
We have to be careful with set comprehensions because of Russell's paradox:
{x : x ∉ x} (both contains and doesn't contain itself)
Restrict set comprehension so that you can't conjure sets out of thin air with them;
instead, you can *only* use set comprehensions to carve out subsets of sets you
already have.
{x : P(x)} <---- not considered a valid set comprehension
Instead, we'll insist on this form:
{x ∈ 𝓤 : P(x)} or {x : x ∈ 𝓤 and P(x)}
We restrict the set comprehension so that every element of the comprehension
must come from set 𝓤 (pronounced "universe") that you've already obtained
by other means.
𝓤 (or "universe") does not mean "all elements", or "all sets", or anything like that
Rather it means: 𝓤 "all elements that I care about"
What the universe is is highly context-dependent.
E.g. if I'm talking about numbers, the universe might be ℕ or ℝ or something
If I'm talking about the set of C programs, it would be something else.
Pow(X) "the set of all subsets of X"
E.g.
{} ⊆ {1,2}
{1} ⊆ {1,2}
{2} ⊆ {1,2}
{1,2} ⊆ {1,2}
Therefore: Pow(X) = {{},{1},{2},{1,2}}
⊂ is to ⊆ as
< is to ≤
For finite sets X, their cardinality is the number of elements they have,
or more formally:
the number of distinct elements x s.t. x ∈ X
|{1,2}| = 2
|{5,6}| = 2
|{5,6,5,6,5,6}| = 2 (because multiple occurences of the same element make no difference)
|{1,2,3}| = 3
x ∈ A ∪ B iff (x ∈ A *or* x ∈ B)
x ∈ A ∩ B iff (x ∈ A *and* x ∈ B)
this tells us that there's some spooky connection
between ∪ and ∨
and ∩ and ∧
..almost as if it wasn't a coincidence that the pointy end is
facing the same the direction??
Two sets are *disjoint* if they have no elements in common.
Or, equivalently, if A ∩ B = ∅
^ This definition has a funny consequence:
there exists a set that is disjoint with itself.
The empty set, because ∅ ∩ ∅ = ∅
The *difference* between A and B
written A \ B or A - B
the set of everything that is in A, but *not* in B
{1,2,3} \ {3,4} = {1,2}
{} \ {1,2,3,4} = {}
....
The *symmetric difference* of A and B
written A ⊕ B
the set of everything that is in *either* A or B, but not both
{1,2} ⊕ {2,3} = {1,3}
⊕ on sets is rather obscure, but most CS people will know its logical equivalent
x ∈ A ⊕ B iff (x ∈ A xor x ∈ B)
(not in)
xor (exclusive or)
The complement of A, written A^C (I can't write superscript here :( )
is: everything that is in the universe 𝓤, but *not* in A
If the universe is ℕ
{1,2,3}^C = {0,4,5,6,...}
this is sometimes called relative complement because it's relative to the universe
(A ∪ B) ∩ C = (A ∩ C) ∪ (A ∩ B)
c.f.
(x + y) * z = (x * z) + (y * z)
Prove: A ∪ A = A
... after the break
A = (identity)
A ∪ ∅ = (complementation)
A ∪ (A ∩ A^C) = (distribution)
(A ∪ A) ∩ (A ∪ A^C) = (compl.)
(A ∪ A) ∩ 𝓤 = (identity)
A ∪ A
QED
^ A = A ∪ A we call a *derived law*
because we can prove it from
the laws of set operations
The Principle of Duality, aka "prove on set equality, get two for free"
says that:
if I've proven a set equality X = Y using the laws of operations,
then the equality still holds if I flip all ∪ and ∩ upside down,
and flip all 𝓤 to ∅ symbols, and vice versa.
dual(X) <--- dual is a function that does this flipping
dual(X ∪ (Y ∩ Z)) = X ∩ (Y ∪ Z)
dual(X ∪ (Y ∩ ∅)) = X ∩ (Y ∪ 𝓤)
Above, we proved A = A ∪ A
By the principle of duality,
it follows immediately that
dual(A) = dual(A ∪ A)
or (simplified)
A = A ∩ A
Why? Intuitively, just take the proof of A = A ∪ A and flip all symbols upside down. Done!
(a bit handwavy, more formal later in the course)
We call (x,y) an *ordered* pair because e.g.
(1,3) is not the same as (3,1)
bottom line: pairs (or tuples in general) are not sets (1,3) is not {1,3}
(1,3) ≠ (3,1) {1,3} = {3,1}
S × T all the ways to pair up elements in S and T
{1,2,3} × {hello,world} = {(1,hello),
(2,hello),
(3,hello),
(1,world),
(2,world),
(3,world)}
Formal languages are to strings as
numbers (ℕ,ℤ,..) are to int,float ...
Intuitively: formal languages are basically sets of strings but it's math not
programming so fancier word
Alphabets are traditionally written Σ (capital sigma)
the elements of an alphabet are often called symbols (think characters)
The alphabet of digits:
Σ = {0,1,2,3,4,5,6,7,8,9}
The alphabet of roman lower-case letters:
Σ = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,x,y,z} (modulo typos)
The main point: alphabets must be finite.
In both of the above examples, every symbol happened to be denoted by a single
character of text; this is *not* required. Symbols can be "any size on the page"
Σ = {hello,world} h is not a symbol of this alphabet, but hello is a symbol
A *word* (over an alphabet Σ) is a finite (possible empty) sequence of symbols from Σ
(when I say "sequence", you can think "array" or "list" and you'll get the general idea)
The empty word (in programming terms: the empty string "")
is written λ or ε
The set of all words over an alphabet Σ
is written Σ^* (sigma-star)
The set of all words over an alphabet Σ *with length exactly k*
is written Σ^k
The set of all *non-empty* words over an alphabet Σ
is written Σ^+
Example:
Let Σ denote the set of all ASCII character (|Σ| = 256)
Then Σ^* is basically the same as the string datatype in most programming languages
(except unbounded)
*Concatenation* is when you mash two strings together
"hello" + "world" = "helloworld"
Concatenation in formal languages is written
either as the empty string (similar to multipliciation)
or as ⬝ (also similar to multiplication)
if V = hello and W = world
VW or V⬝W is helloworld
We can talk about the length of words
length(hello) = 5
length(λ) = 0 (because λ denotes the empty word)
Algebraic laws about concatenation:
wλ = λw = w (identity)
xyz = (xy)z = x(yz) (associativity)
("h" + "x") + "w" = "hx" + "w" = "hxw"
"h" + ("x" + "w") = "h" + "xw" = "hxw"
We don't have commutativity though, because
"hello" + "world" ≠ "world" + "hello"
When we say *language* here, we basically mean "set of strings"
in many contexts, a language is more than just a set of strings,
e.g. English isn't just random characters, it also means stuff
But in the context of formal language theory, we're not concerned with
meaning, we're just concerned with which words are in a language or not.
The set of C programs is a language, or more precisely:
the set of valid C programs is a subsets of Σ* where Σ is the ASCII (or whatever) alphabet
one job of a compiler is to determine: is your C program in this subset or not? If not, syntax error
If we're very (infinitely) patient, we could define the set of C programs by explicit enumeration:
𝓒 = { int main() {},
int main() {return 1;},
.... }
... but nobody has time for that, so usually you would carve out from the alphabet the subset that
obeys certain rules. (formally using set comprehensions)
^ these rules usually take the form of a *grammar*
-.-.-.-.-.-.---.-.-.-...-.-.-- (in Σ^* but not a number)
Concatenation of language X and Y
is: all the words the can be formed by concatenating a word from X and a word from Y
X = {hello,world}
Y = {hi,planet}
XY = {hellohi,helloplanet,worldhi,worldplanet}
Kleene star X^*
all the words that can be formed by concenating 0 or more words from X
X = {hello,hi}
X^* = {λ,hello,hi,hellohello,hihi,hellohi,hihello,...}
Y = {hi}
Y^* = {λ,hi,hihi,hihihi,hihihihihi,...}
(Fun fact: X^*⬝(X^*) = X^*⬝X^*)
X⬝(X^*) = X^* \ {λ}